import java.util.ArrayList;

public class TrafficAssignment {
	static int[][] connectionArray = {
			{ 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0 },
			{ 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 },
			{ 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
			{ 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
			{ 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } };
	static int[][] capacityMatrix = {
			{ 0, 1500, 0, 1500, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1500,
					1500, 0, 0 },
			{ 1500, 0, 1500, 0, 2250, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
					2250, 0 },
			{ 0, 1500, 0, 0, 0, 1500, 0, 0, 0, 1500, 0, 0, 0, 0, 0, 0, 0, 0, 0,
					0, 1500 },
			{ 1500, 0, 0, 0, 2250, 0, 1500, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2250, 0,
					0, 0, 0 },
			{ 0, 2250, 0, 2250, 0, 2250, 0, 2250, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
					0, 0, 0 },
			{ 0, 0, 1500, 0, 2250, 0, 0, 0, 1500, 0, 2250, 0, 0, 0, 0, 0, 0, 0,
					0, 0, 0 },
			{ 0, 0, 0, 1500, 0, 0, 0, 1500, 0, 0, 0, 0, 0, 0, 1500, 1500, 0, 0,
					0, 0, 0 },
			{ 0, 0, 0, 0, 2250, 0, 1500, 0, 1500, 0, 0, 0, 0, 2250, 0, 0, 0, 0,
					0, 0, 0 },
			{ 0, 0, 0, 0, 0, 1500, 0, 1500, 0, 0, 0, 1500, 1500, 0, 0, 0, 0, 0,
					0, 0, 0 },
			{ 0, 0, 1500, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 2250, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 0, 0, 1500, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 0, 0, 1500, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 0, 2250, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 1500, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 1500, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 2250, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 1500, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 1500, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 2250, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 1500, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } };

	static int[][] freeflowMatrix = {
			{ 0, 39, 0, 39, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 40, 39, 0, 0 },
			{ 39, 0, 53, 0, 37, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 36, 0 },
			{ 0, 53, 0, 0, 0, 39, 0, 0, 0, 43, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 30 },
			{ 39, 0, 0, 0, 49, 0, 53, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 0, 0, 0, 0 },
			{ 0, 37, 0, 49, 0, 57, 0, 50, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 39, 0, 50, 0, 0, 0, 52, 0, 27, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 53, 0, 0, 0, 43, 0, 0, 0, 0, 0, 0, 39, 30, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 57, 0, 43, 0, 57, 0, 0, 0, 0, 47, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 52, 0, 57, 0, 0, 0, 29, 56, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 43, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 27, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 0, 0, 29, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 0, 0, 56, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 0, 47, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 39, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 30, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 39, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 36, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 30, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } };
	static int[][] zeroMatrix={
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } };
	
	static int[][] referenceResults={
		{0,1737,0,591,0,0,0,0,0,0,0,0,0,0,0,0,0,960,960,0,0},
		{877,0,1665,0,1569,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1440,0},
		{0,570,0,0,0,1943,0,0,0,960,0,0,0,0,0,0,0,0,0,0,960},
		{1451,0,0,0,1639,0,904,0,0,0,0,0,0,0,0,0,1440,0,0,0,0},
		{0,1804,0,1667,0,1572,0,1614,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,848,0,1925,0,0,0,1545,0,1440,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,1736,0,0,0,688,0,0,0,0,0,0,960,960,0,0,0,0,0},
		{0,0,0,0,1524,0,1521,0,819,0,0,0,0,1440,0,0,0,0,0,0,0},
		{0,0,0,0,0,803,0,1561,0,0,0,960,960,0,0,0,0,0,0,0,0},
		{0,0,960,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,0,0,1440,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,0,0,0,0,0,960,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,0,0,0,0,0,960,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,0,0,0,0,1440,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,0,0,0,960,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,0,0,0,960,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,1440,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{960,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{960,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,1440,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,960,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}};

	static int[][] ODMatrix = {{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,0,0,0,0,0,0,0,0,0,60,120,60,120,180,180,60,120,60},
		{0,0,0,0,0,0,0,0,0,0,0,0,75,120,75,270,360,270,75,120,75},
		{0,0,0,0,0,0,0,0,0,0,0,0,60,120,60,180,180,120,60,120,60},
		{0,0,0,0,0,0,0,0,0,60,120,60,0,0,0,60,120,60,120,180,180},
		{0,0,0,0,0,0,0,0,0,75,120,75,0,0,0,75,120,75,270,360,270},
		{0,0,0,0,0,0,0,0,0,60,120,60,0,0,0,60,120,60,180,180,120},
		{0,0,0,0,0,0,0,0,0,120,180,180,60,120,60,0,0,0,60,120,60},
		{0,0,0,0,0,0,0,0,0,270,360,270,75,120,75,0,0,0,75,120,75},
		{0,0,0,0,0,0,0,0,0,180,180,120,60,120,60,0,0,0,60,120,60},
		{0,0,0,0,0,0,0,0,0,60,120,60,120,180,180,60,120,60,0,0,0},
		{0,0,0,0,0,0,0,0,0,75,120,75,270,360,270,75,120,75,0,0,0},
		{0,0,0,0,0,0,0,0,0,60,120,60,180,180,120,60,120,60,0,0,0}};

	static int[][] directionMatrix = {
			{ 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0 },
			{ -1, 0, -1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 },
			{ 0, -1, 0, 0, 0, 1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
			{ 1, 0, 0, 0, -1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0 },
			{ 0, 1, 0, -1, 0, -1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 1, 0, -1, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 1, 0, -1, 0, -1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } };

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		ArrayList<NetworkLink> linkArray = new ArrayList<NetworkLink>();
		ArrayList<NetworkNode> nodeArray = new ArrayList<NetworkNode>();
		for (int i = 0; i < connectionArray[0].length; i++) {
			NetworkNode node = new NetworkNode();
			node.setNodeID(i);
			nodeArray.add(node);
		}
		for (int i = 0; i < connectionArray[0].length; i++) {
			for (int j = 0; j < connectionArray[0].length; j++) {
				if (connectionArray[i][j] == 1) {
					int capacity = capacityMatrix[i][j];
					int freeflowTravelTime = freeflowMatrix[i][j];
					int direction = directionMatrix[i][j];
					NetworkLink link = new NetworkLink(i * 100 + j, capacity,
							freeflowTravelTime, i, j, direction);
					linkArray.add(link);
					NetworkNode fromNode = nodeArray.get(i);
					NetworkNode toNode = nodeArray.get(j);
					if (direction == 1) {
						fromNode.getGoingLinksNS().add(link);
						toNode.getComingLinksNS().add(link);
					} else {
						fromNode.getGoingLinksEW().add(link);
						toNode.getComingLinksEW().add(link);
					}

				}
			}

		}
		// return;
//		DijkstraShortestPath(linkArray, nodeArray, 0);
		trafficAssignment_NoneorAll(linkArray, nodeArray);
	}

	static ArrayList<ArrayList<NetworkPath>> trafficAssignment_NoneorAll(
			ArrayList<NetworkLink> links, ArrayList<NetworkNode> nodes) {
		ArrayList<ArrayList<NetworkPath>> pathsArray=new ArrayList<>();
		for(int i=9;i<nodes.size();i++)
		{
			ArrayList<NetworkPath> paths=DijkstraShortestPath(links, nodes, i);
			for (int j=9; j<paths.size();j++)
			{
				NetworkPath path = paths.get(j);
				for(NetworkLink link:path.getPathLinks())
				{
					link.flow=link.flow+ODMatrix[i][j];
				}
			}
		}
		ArrayList<NetworkLink> lastIterationLinks=new ArrayList<>();
		for (int i=0;i<links.size();i++)
		{
			NetworkLink link=links.get(i);
//			System.out.println((link.getFromNodeID()+1)+"---->" +(link.getToNodeID()+1)+": volume: "+link.getFlow());
			link.setTravelTime(link.calculateTravelTime());
			NetworkLink lastIterationLink=new NetworkLink(link);
			lastIterationLinks.add(lastIterationLink);
			
//			link.setFlow(0);
		}
		SignalUtil.calculateControlDelay(lastIterationLinks, nodes);
		SignalUtil.calculateControlDelay(links, nodes);
		for (int i=0;i<links.size();i++)
		{
			NetworkLink link=links.get(i);
			link.setFlow(0);
		}
		for(int i=9;i<nodes.size();i++)
		{
			ArrayList<NetworkPath> paths=DijkstraShortestPath(links, nodes, i);
			for (int j=9; j<paths.size();j++)
			{
				NetworkPath path = paths.get(j);
				for(NetworkLink link:path.getPathLinks())
				{
					link.flow=link.flow+ODMatrix[i][j];
				}
			}
		}
		ArrayList<NetworkLink> currentIterationLinks=new ArrayList<>();
		for (int i=0;i<links.size();i++)
		{
			NetworkLink link=links.get(i);
//			System.out.println((link.getFromNodeID()+1)+"---->" +(link.getToNodeID()+1)+": volume: "+link.getFlow());
			link.setTravelTime(link.calculateTravelTime());
			NetworkLink currentIterationLink=new NetworkLink(link);
			currentIterationLinks.add(currentIterationLink);
			
//			link.setFlow(0);
		}
		SignalUtil.calculateControlDelay(currentIterationLinks, nodes);
		SignalUtil.calculateControlDelay(links, nodes);
		for (int i=0;i<links.size();i++)
		{
			NetworkLink link=links.get(i);
			link.setFlow(0);
		}
		ArrayList<NetworkLink> solutionLinks=new ArrayList<>();
		for (int i=0;i<links.size();i++)
		{
			NetworkLink link=links.get(i);
//			System.out.println((link.getFromNodeID()+1)+"---->" +(link.getToNodeID()+1)+": volume: "+link.getFlow());
			NetworkLink solutionLink=new NetworkLink(link);
			solutionLinks.add(solutionLink);
//			double lemuda=0;
//			double temp=lastIterationLinks.get(i).flow*lemuda+currentIterationLinks.get(i).flow*(1-lemuda);
//			solutionLink.flow=(int)(temp);
//			solutionLink.setTravelTime(solutionLink.calculateTravelTime());
			
		}
		long objectiveFunctionValue=1000000000;
		long lastObjectiveFunctionValue=objectiveFunctionValue;
		double lemuda=0;
		for (double l=0;l<=1;l=l+0.0001)
		{
			long tempFunctionValue=0;
			for (int i=0;i<links.size();i++)
			{
				NetworkLink solutionLink=solutionLinks.get(i);						
				double temp=lastIterationLinks.get(i).flow*l+currentIterationLinks.get(i).flow*(1-l);
				solutionLink.flow=(int)(temp);
				solutionLink.setTravelTime(solutionLink.calculateTravelTime());		
				tempFunctionValue=tempFunctionValue+solutionLink.getTravelTime()*solutionLink.getFlow();
			}
			if(tempFunctionValue<objectiveFunctionValue)
			{
				lemuda=l;
				objectiveFunctionValue=tempFunctionValue;
			}
				
			
		}
		for (int i=0;i<links.size();i++)
		{
			NetworkLink solutionLink=solutionLinks.get(i);						
			double temp=lastIterationLinks.get(i).flow*lemuda+currentIterationLinks.get(i).flow*(1-lemuda);
			solutionLink.flow=(int)(temp);
			solutionLink.setTravelTime(solutionLink.calculateTravelTime());	
//			System.out.println((solutionLink.getFromNodeID()+1)+"---->" +(solutionLink.getToNodeID()+1)+": volume: "+solutionLink.getFlow());
			
		}
		
		for (int i=0;i<links.size();i++)
		{
			NetworkLink solutionLink=solutionLinks.get(i);					
			NetworkLink currentLink=currentIterationLinks.get(i);
			NetworkLink lastLink=lastIterationLinks.get(i);
			System.out.println("solution"+(solutionLink.getFromNodeID()+1)+"---->" +(solutionLink.getToNodeID()+1)+": volume: "+solutionLink.getFlow());
			System.out.println("current"+(currentLink.getFromNodeID()+1)+"---->" +(currentLink.getToNodeID()+1)+": volume: "+currentLink.getFlow());
			System.out.println("last"+(currentLink.getFromNodeID()+1)+"---->" +(currentLink.getToNodeID()+1)+": volume: "+lastLink.getFlow());
		}
		//loop
		double convergence;
		double convergence_1=0;
		double convergence_2=0;
		for (int i=0;i<links.size();i++)
		{
			NetworkLink solutionLink=solutionLinks.get(i);					
			NetworkLink currentLink=currentIterationLinks.get(i);
			NetworkLink lastLink=lastIterationLinks.get(i);
//			System.out.println("solution"+(solutionLink.getFromNodeID()+1)+"---->" +(solutionLink.getToNodeID()+1)+": volume: "+solutionLink.getFlow());
//			System.out.println("current"+(currentLink.getFromNodeID()+1)+"---->" +(currentLink.getToNodeID()+1)+": volume: "+currentLink.getFlow());
//			System.out.println("last"+(currentLink.getFromNodeID()+1)+"---->" +(currentLink.getToNodeID()+1)+": volume: "+lastLink.getFlow());
			convergence_1=convergence_1+Math.pow(solutionLink.flow-lastLink.flow,2);
			convergence_2=convergence_2+lastLink.flow;
		}
		convergence=Math.sqrt((double)convergence_1)/(double)convergence_2;
		int interationNumber=1;
		System.out.println("Minimum function result is: lemuda = "+lemuda+"; objective function = "+objectiveFunctionValue+"; last objective function=:"+lastObjectiveFunctionValue);
//		while(Math.abs(lastObjectiveFunctionValue-objectiveFunctionValue)>10000)
		while(convergence>0.001)
		{
			lastObjectiveFunctionValue=objectiveFunctionValue;
			lastIterationLinks.clear();
			for (int i=0;i<links.size();i++)
			{
				NetworkLink link=links.get(i);
				NetworkLink solutionLink=solutionLinks.get(i);			
//				System.out.println((link.getFromNodeID()+1)+"---->" +(link.getToNodeID()+1)+": volume: "+link.getFlow());
				solutionLink.setTravelTime(solutionLink.calculateTravelTime());
				NetworkLink lastIterationLink=new NetworkLink(solutionLink);
				lastIterationLinks.add(lastIterationLink);
//				link.setFlow(0);
				link.setTravelTime(solutionLink.calculateTravelTime());
				
			}
			SignalUtil.calculateControlDelay(lastIterationLinks, nodes);
			SignalUtil.calculateControlDelay(links, nodes);
			for (int i=0;i<links.size();i++)
			{
				NetworkLink link=links.get(i);
				link.setFlow(0);
			}
			currentIterationLinks.clear();		
			solutionLinks.clear();

			
			for(int i=9;i<nodes.size();i++)
			{
				ArrayList<NetworkPath> paths=DijkstraShortestPath(links, nodes, i);
				for (int j=9; j<paths.size();j++)
				{
					NetworkPath path = paths.get(j);
					for(NetworkLink link:path.getPathLinks())
					{
						link.flow=link.flow+ODMatrix[i][j];
					}
				}
			}
			
			for (int i=0;i<links.size();i++)
			{
				NetworkLink link=links.get(i);
//				System.out.println((link.getFromNodeID()+1)+"---->" +(link.getToNodeID()+1)+": volume: "+link.getFlow());
				link.setTravelTime(link.calculateTravelTime());
				NetworkLink currentIterationLink=new NetworkLink(link);				
				
				currentIterationLinks.add(currentIterationLink);
//				link.setFlow(0);
			}
			SignalUtil.calculateControlDelay(currentIterationLinks, nodes);
			SignalUtil.calculateControlDelay(links, nodes);
			for (int i=0;i<links.size();i++)
			{
				NetworkLink link=links.get(i);
				link.setFlow(0);
			}
			
			for (int i=0;i<links.size();i++)
			{
				NetworkLink link=links.get(i);

				NetworkLink solutionLink=new NetworkLink(link);
				solutionLinks.add(solutionLink);

				
			}
			
			
			lemuda=0;
			for (double l=0;l<=1;l=l+0.0001)
			{
				long tempFunctionValue=0;
				for (int i=0;i<links.size();i++)
				{
					NetworkLink solutionLink=solutionLinks.get(i);						
					double temp=lastIterationLinks.get(i).flow*l+currentIterationLinks.get(i).flow*(1-l);
					solutionLink.flow=(int)(temp);
					solutionLink.setTravelTime(solutionLink.calculateTravelTime());		
					tempFunctionValue=tempFunctionValue+solutionLink.getTravelTime()*solutionLink.getFlow();
				}
				if(tempFunctionValue<objectiveFunctionValue)
				{
					lemuda=l;
					objectiveFunctionValue=tempFunctionValue;
				}
					
				
			}
			for (int i=0;i<links.size();i++)
			{
				NetworkLink solutionLink=solutionLinks.get(i);						
				double temp=lastIterationLinks.get(i).flow*lemuda+currentIterationLinks.get(i).flow*(1-lemuda);
				solutionLink.flow=(int)(temp);
				solutionLink.setTravelTime(solutionLink.calculateTravelTime());	
//				System.out.println((solutionLink.getFromNodeID()+1)+"---->" +(solutionLink.getToNodeID()+1)+": volume: "+solutionLink.getFlow());
				
			}
			interationNumber=interationNumber+1;
			convergence_1=0;
			convergence_2=0;
			for (int i=0;i<links.size();i++)
			{
				NetworkLink solutionLink=solutionLinks.get(i);					
				NetworkLink currentLink=currentIterationLinks.get(i);
				NetworkLink lastLink=lastIterationLinks.get(i);
//				System.out.println("solution"+(solutionLink.getFromNodeID()+1)+"---->" +(solutionLink.getToNodeID()+1)+": volume: "+solutionLink.getFlow());
//				System.out.println("current"+(currentLink.getFromNodeID()+1)+"---->" +(currentLink.getToNodeID()+1)+": volume: "+currentLink.getFlow());
//				System.out.println("last"+(currentLink.getFromNodeID()+1)+"---->" +(currentLink.getToNodeID()+1)+": volume: "+lastLink.getFlow());
				convergence_1=convergence_1+Math.pow(solutionLink.flow-lastLink.flow,2);
				convergence_2=convergence_2+lastLink.flow;
			}
			convergence=Math.sqrt((double)convergence_1)/(double)convergence_2;
			//output
			int[][] results=zeroMatrix.clone();
			for (int i=0;i<links.size();i++)
			{
				NetworkLink solutionLink=solutionLinks.get(i);					
				NetworkLink currentLink=currentIterationLinks.get(i);
				NetworkLink lastLink=lastIterationLinks.get(i);
				System.out.println("solution"+(solutionLink.getFromNodeID()+1)+"---->" +(solutionLink.getToNodeID()+1)+": volume: "+solutionLink.getFlow());
//				System.out.println("current"+(currentLink.getFromNodeID()+1)+"---->" +(currentLink.getToNodeID()+1)+": volume: "+currentLink.getFlow());
//				System.out.println("last"+(currentLink.getFromNodeID()+1)+"---->" +(currentLink.getToNodeID()+1)+": volume: "+lastLink.getFlow());
				results[solutionLink.getFromNodeID()][solutionLink.getToNodeID()]=solutionLink.getFlow();
			}
			
			//output
//			
			
			
			System.out.println(interationNumber+" : lemuda = "+lemuda+"; objective function = "+objectiveFunctionValue+"; last objective function=:"+lastObjectiveFunctionValue);
			for(int i=0;i<results.length;i++)
			{
				
				for(int j=0;j<results.length;j++)
				{
					System.out.print(results[i][j]+", ");
				}
				System.out.println();
			}
			System.out.println();
			for(int i=0;i<referenceResults.length;i++)
			{
				
				for(int j=0;j<referenceResults.length;j++)
				{
					System.out.print(referenceResults[i][j]+", ");
				}
				System.out.println();
			}
			
			
			

		}
		
				return null;
	}

	static ArrayList<NetworkPath> DijkstraShortestPath(
			ArrayList<NetworkLink> links, ArrayList<NetworkNode> nodes,
			int originNodeID) {
		ArrayList<NetworkPath> paths = new ArrayList<NetworkPath>();
		// ArrayList<NetworkNode> newNodes=new ArrayList<>();
		// ArrayList<NetworkNode> unVisitedNodes=new ArrayList<>();
		ArrayList<NetworkNode> neighborNodes = new ArrayList<>();

		// ArrayList<NetworkNode> visitedNodes=new ArrayList<>();
		// for (int i=0;i<nodes.size();i++)
		// {
		// NetworkNode newNode=new NetworkNode(nodes.get(i));
		//
		// newNodes.add(newNode);
		// }

		NetworkNode origineNode = nodes.get(originNodeID);
		NetworkNode currentNode = origineNode;
		currentNode.label = 0;
		for (int i = 0; i < nodes.size(); i++) {
			NetworkPath path = new NetworkPath(origineNode, nodes.get(i),
					100000000);
			paths.add(path);
		}

		// get neighbor nodes and their label numbers
		for (int m = 0; m < currentNode.getGoingLinksEW().size(); m++) {
			NetworkLink goingLink = currentNode.getGoingLinksEW().get(m);
			NetworkNode neighborNode = nodes.get(goingLink.getToNodeID());
			if (neighborNode.visited) {
				continue;
			}
			int distance = currentNode.label + goingLink.getTravelTime();
			if (distance < neighborNode.label) {
				neighborNode.label = distance;
				ArrayList<NetworkLink> currentNodePath = paths.get(
						currentNode.nodeID).getPathLinks();

				paths.get(neighborNode.nodeID).setPathLinks(
						(ArrayList<NetworkLink>) currentNodePath.clone());
				paths.get(neighborNode.nodeID).getPathLinks().add(goingLink);
				paths.get(neighborNode.nodeID).value = distance;
			}
			neighborNodes.add(neighborNode);
		}
		for (int m = 0; m < currentNode.getGoingLinksNS().size(); m++) {
			NetworkLink goingLink = currentNode.getGoingLinksNS().get(m);
			NetworkNode neighborNode = nodes.get(goingLink.getToNodeID());
			if (neighborNode.visited) {
				continue;
			}
			int distance = currentNode.label + goingLink.getTravelTime();
			if (distance < neighborNode.label) {
				neighborNode.label = distance;
				ArrayList<NetworkLink> currentNodePath = paths.get(
						currentNode.nodeID).getPathLinks();

				paths.get(neighborNode.nodeID).setPathLinks(
						(ArrayList<NetworkLink>) currentNodePath.clone());
				paths.get(neighborNode.nodeID).getPathLinks().add(goingLink);
				paths.get(neighborNode.nodeID).value = distance;
			}
			neighborNodes.add(neighborNode);
		}

		// set the origin one as visited
		currentNode.visited = true;
		while (neighborNodes.size() > 0) {
			// select the next current node, which has the minimum label number
			// in neighbornodes.
			NetworkNode selectedNeighborNode;
			selectedNeighborNode = neighborNodes.get(0);
			for (int m = 1; m < neighborNodes.size(); m++) {
				NetworkNode tempNode = neighborNodes.get(m);
				if (selectedNeighborNode.label > tempNode.label) {
					selectedNeighborNode = tempNode;
					// neighborNodes.remove(m);
					break;
				}

			}
			currentNode = selectedNeighborNode;
			neighborNodes.remove(selectedNeighborNode);

			// //get neighbor nodes and their label numbers
			for (int m = 0; m < currentNode.getGoingLinksEW().size(); m++) {
				NetworkLink goingLink = currentNode.getGoingLinksEW().get(m);
				NetworkNode neighborNode = nodes.get(goingLink.getToNodeID());
				if (neighborNode.visited) {
					continue;
				}
				int distance = currentNode.label + goingLink.getTravelTime();
				if (distance < neighborNode.label) {
					neighborNode.label = distance;
					ArrayList<NetworkLink> currentNodePath = paths.get(
							currentNode.nodeID).getPathLinks();

					paths.get(neighborNode.nodeID).setPathLinks(
							(ArrayList<NetworkLink>) currentNodePath.clone());
					paths.get(neighborNode.nodeID).getPathLinks()
							.add(goingLink);
					paths.get(neighborNode.nodeID).value = distance;
				}
				neighborNodes.add(neighborNode);
			}
			for (int m = 0; m < currentNode.getGoingLinksNS().size(); m++) {
				NetworkLink goingLink = currentNode.getGoingLinksNS().get(m);
				NetworkNode neighborNode = nodes.get(goingLink.getToNodeID());
				if (neighborNode.visited) {
					continue;
				}
				int distance = currentNode.label + goingLink.getTravelTime();
				if (distance < neighborNode.label) {
					neighborNode.label = distance;
					ArrayList<NetworkLink> currentNodePath = paths.get(
							currentNode.nodeID).getPathLinks();

					paths.get(neighborNode.nodeID).setPathLinks(
							(ArrayList<NetworkLink>) currentNodePath.clone());
					paths.get(neighborNode.nodeID).getPathLinks()
							.add(goingLink);
					paths.get(neighborNode.nodeID).value = distance;
				}
				neighborNodes.add(neighborNode);
			}

			// set the origin one as visited
			currentNode.visited = true;
		}
		for(int i=0;i<nodes.size();i++)
		{
			nodes.get(i).reInitiate();
		}
		// NetworkPath path=new NetworkPath();
		
		//output 
		for(int i=0;i<paths.size();i++)
		{
			NetworkPath path=paths.get(i);
			for (int j=0;j<path.getPathLinks().size();j++)
			{
				System.out.print((path.getPathLinks().get(j).fromNodeID+1)+"->"+(path.getPathLinks().get(j).toNodeID+1)+",");
			}
			System.out.print(" : value"+path.value+"\n\r");
		}
		return paths;
	}
	
}


